{ INFORMATICS.MCCME.RU
  Problem statement: http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=2783
  Verdict: Accepted
}
uses
	SysUtils, Math; 
 
const
	INF:int64 = maxlongint;
 
var
	n,m,x,y,cur,h,t,v,kk,cf,prev,i,ans:longint;
	c,f:array[0..110,0..110] of int64;
	q,from:array[0..110] of int64;
 
begin
reset(input,'input.txt');
rewrite(output,'output.txt');
read(n,m);
for i:=1 to m do begin
	read(x,y,cur);
	dec(x);
	dec(y);
	c[x][y]:=cur;
end;
kk:=n-1;
while true do begin
	fillchar(from,sizeof(from),-1);
	h:=0;
	t:=0;
	q[0]:=0;
	inc(t);
	from[0] := 0;
	while h < t do begin
		cur := q[h];
		inc(h);
		for v:=0 to kk do
			if (from[v] = -1) and (c[cur][v]-f[cur][v] > 0) then begin
				q[t]:=v;
				inc(t);
				from[v] := cur;
			end;
	end;
	if from[n-1] = -1 then break;
	cf:=INF;
	cur := n - 1;
	while cur <> 0 do begin
		prev := from[cur];
		cf := min(cf, c[prev][cur] - f[prev][cur]);
		cur := prev;
	end;
	cur := n - 1;
	while cur <> 0 do begin
		prev := from[cur];
		inc(f[prev][cur], cf);
		dec(f[cur][prev], cf);
		cur := prev;
	end;
end;
ans := 0;
for i:=0 to kk do
	if c[0][i] > 0 then inc(ans,f[0][i]);
write(ans);
end.